/**
 * 
 */
package leetCode;

import java.util.ArrayList;

import javax.naming.InsufficientResourcesException;

/**
 * @author zhongfang
 *
 */
public class LowestCommonAncestorofaBinarySearchTree {
	 public class TreeNode {
	      int val;
	      TreeNode left;
	      TreeNode right;
	      TreeNode(int x) { val = x; }
	  }
	    ArrayList<TreeNode> pList;
	    ArrayList<TreeNode> qList;
	   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
	       getPath(root,p,q,new ArrayList<TreeNode>());
	       int i=0;
	       int minL=Math.min(pList.size(),qList.size());
	       while (true) {
	    	   if(i==minL-1){
	    		   break;
	    	   }
	    	   if(pList.get(i+1)!=pList.get(i+1)){
	    		   break;
	    	   }
	    	   i++;
	       }
	       return pList.get(i-1);
	   }
	   public void getPath(TreeNode root,TreeNode p,TreeNode q,ArrayList<TreeNode> curPath){
	       if(root==p){
	           curPath.add(root);
	           pList=curPath;
	           if(qList!=null){//如果p和q都已经找到，可以不用递归下去
	               return;
	           }
	       }
	       if(root==q){
	           curPath.add(root);
	           qList=curPath;
	           if(pList!=null){
	               return;
	           }
	       }
	       if(root==null)
	    	   return;
	       
	       curPath.add(root);
	       if(root.left!=null){
	           getPath(root.left,p,q,new ArrayList<TreeNode>(curPath));
	       }
	       if(root.right!=null){
               getPath(root.right,p,q,new ArrayList<TreeNode>(curPath));
	       }
	   }
	   public static void main(String[] args) {
		LowestCommonAncestorofaBinarySearchTree lowestCommonAncestorofaBinarySearchTree=new LowestCommonAncestorofaBinarySearchTree();
		TreeNode node=lowestCommonAncestorofaBinarySearchTree.new TreeNode(2);
		TreeNode node1=lowestCommonAncestorofaBinarySearchTree.new TreeNode(3);
		node.right=node1;
//		System.out.println(lowestCommonAncestorofaBinarySearchTree.lowestCommonAncestor(node, node, node1).val);
	}
}
